package com.fallsvc.re.javasesets.ebtree;

/**
 * @auther falls_vc
 * description:
 * @date 2025/10/20  10:23
 */
public class Demo1 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 相同树
    public boolean isSameTree(TreeNode root,TreeNode t) {
        if(root == null && t == null) return true;
        if((root == null && t != null) || (root != null && t == null)) return false;
        if(root.val != t.val) return false;

        return isSameTree(root.left,t.left)&&isSameTree(root.right,t.right);
    }

    // 前序和中序生成树
    public int preIndex=0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inStart, int inEnd) {
        if(inStart>inEnd) return null;

        TreeNode root=new TreeNode(preorder[preIndex]);
        //找到该值在中序遍历 数组的下标
        int finVal=findIndex(inorder,preorder[preIndex],inStart,inEnd);
        if(finVal<0) System.exit(0); //中序遍历中没有找到前序遍历中的值

        preIndex++;

        root.left=buildTreeChild(preorder,inorder,inStart,finVal-1);
        root.right=buildTreeChild(preorder,inorder,finVal+1,inEnd);

        return root;
    }

    private int findIndex(int[] inorder, int key, int inStart, int inEnd) {
        for (int i = inStart; i <=inEnd ; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }

    // 中序和后序
    public int prePostIndex;
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        prePostIndex = inorder.length - 1;

        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild1(int[] inorder, int[] postorder,int s,int e) {
        if(s > e) return null;

        TreeNode root = new TreeNode(postorder[prePostIndex--]);
        int ret = findIndexValInInorder(inorder,root.val,s,e);
        if(ret == -1)  System.exit(0);

        root.right = buildTreeChild(inorder,postorder,ret+1,e);
        root.left = buildTreeChild(inorder,postorder,s,ret-1);

        return root;
    }

    public int findIndexValInInorder(int[] inorder,int val,int s,int e){
        for(int i = s;i <= e;i++){
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
